1. Field
The present embodiments relate to an art for optimizing a large-scale program.
2. Description of the Related Art
Generally, throughput of a processor improves in accordance with an increase in operating frequency of the processor or improves by parallel execution of instructions. However, increasing the operating frequency results in increased power consumption of the processor. Further, to increase the operating frequency, the miniaturization of the structure of elements is required. The problem of power consumption and the problem of physical limitation due to the miniaturization of the elements make it difficult to realize further improvement in throughput of the processor.
It is known that the number of instructions that the processor can process in parallel is about two to four. Adopting a method such as speculative execution of the processing can realize a certain degree of improvement in parallelism, but it has been known that this method has a limit as well. Parallelizing a program into segments with a larger granularity than that of an instruction level and executing the resultant program by a plurality of processors improves execution efficiency of the program and lessens the above-mentioned problem of the throughput of the processor.
Furthermore, it is known a method in which parallelism latent in a program is extracted from a sequential program. In this method, among statements of the program, data- and control-dependent relationships are extracted, and a program dependence graph is generated based on the dependent relationships. The program dependence graph is a graph representing the meaning of the program using vertices, which represent the statements, and edges which represent the control-dependent relationships and the data-dependent relationships. The program dependence graph handles the control-dependent relationships and thus has a feature of enabling the optimization beyond the control flow. Further, the program dependence graph has a feature for facilitating the optimization since it represents the data-dependent relationships and the control-dependence relationships.
Furthermore, it is known that a program dependence graph can represent the meaning of a program.
Furthermore, it is known that if program dependence graphs of two programs are isomorphic, these programs are semantically equivalent.
Furthermore, it is known that an art to create a semantically equivalent control flow graph from a program dependence graph under a certain restriction condition.
The program dependence graph is a graph in which vertices represent statements or substitution expressions. For example, when several procedures or the like are targets, analysis based on the program dependence graph is possible since the number of vertices is about several tens. However, as for large-scale software, the number of vertices of a graph amounts to several thousands to several ten thousands if vertices represent statements or substitution expressions. It is generally known that a program optimization problem using a program dependence graph becomes an exponential function of the scale of the graph. Therefore, it is difficult to extract parallelism in the whole program with a realistic source and in a realistic time, based on a conventional program dependence graph in which a unit of the extraction is a statement.
Further, when the program dependence graph is made to be contracted, it is requisite that correct program codes can be generated from the contracted program dependence graph (invertibility). A program dependence graph whose invertibility is not ensured cannot be used in program optimization.